//给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
//如果 needle 不是 haystack 的一部分，则返回 -1 。
//
//
//
// 示例 1：
//
//
//输入：haystack = "sadbutsad", needle = "sad"
//输出：0
//解释："sad" 在下标 0 和 6 处匹配。
//第一个匹配项的下标是 0 ，所以返回 0 。
//
//
// 示例 2：
//
//
//输入：haystack = "leetcode", needle = "leeto"
//输出：-1
//解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
//
//
//
//
// 提示：
//
//
// 1 <= haystack.length, needle.length <= 10⁴
// haystack 和 needle 仅由小写英文字符组成
//
//
// Related Topics 双指针 字符串 字符串匹配 👍 1847 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function strStr(haystack: string, needle: string): number {
    function getNext(str: string): number[] {
        let next: number[] = [];
        let j: number = 0;
        //? 初始化时j指0 i指1
        next[0] = j;
        //? 求最长相同前后缀长度 弄到next数组里
        for (let i = 1, length = str.length; i < length; i++) {
            //? 匹配串此时两个值不同
            while (j > 0 && str[i] !== str[j]) {
                //? 使j跳到前一个最大相同前后缀长度的位置，即跳到最大相同前缀之后的位置
                j = next[j - 1];
            }
            if (str[i] === str[j]) {
                //? 如果j！==0 找到两个相同了 j++
                j++;
            }
            //? j为0 或者j为next + 1的值
            next[i] = j;
        }
        return next;
    }
    if (needle.length === 0) return 0;
    let next: number[] = getNext(needle);
    let j: number = 0;
    for (let i = 0, length = haystack.length; i < length; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            //? 使j跳到前一个最大相同前后缀长度的位置，即跳到最大相同前缀之后的位置
            j = next[j - 1];
        }
        if (haystack[i] === needle[j]) {
            //? j最后了 当然 j可能到不了最后
            if (j === needle.length - 1) {
                return i - j;
            }
            j++;
        }
    }
    return -1;
};
//leetcode submit region end(Prohibit modification and deletion)
